← All Articles

[BAEKJOON] 16562. 친구비

Posted on

문제 :

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.


입력 :

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.

두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다.


출력 :

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.



풀이 :

골드 3 문제에다가 서강대학교 프로그래밍 대회 기출문제다 보니 어려울 거라 생각했지만 생각보다 간단한 문제였다.

말 그대로 연결된 무리만 제대로 찾아준다면 문제는 어렵지 않게 풀 수 있었다.

단순히 bfs를 통해 무리를 판단하는 방법과 disjoint set 방법을 사용할까 고민하다가 bfs 방법이 구현은 훨씬 단순하지 않을까 생각하여 쉽게 구현했다.

  1. BFS 방식으로 하나의 무리 최소 친구비용을 구해 비용합에 더해준다.
  2. 모든 무리들을 찾기 위해 1번 과정을 반복한다.
  3. 모든 무리를 찾은 후에는 비용합과 현재 비용을 비교하여 현재 비용보다 비용합이 높을 경우 “Oh no”를 출력, 낮을 경우는 비용합을 출력한다.


코드 :

코드 보기/접기 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
vector<vector<int>> adj;
int *cost, costsum;
bool *checked;

void initializer(int n) {
    cost = new int[n + 1];
    checked = new bool[n + 1]{false};
    adj.resize(n + 1);
}

void bfs(int cur) {
    queue<int> q;
    int mincost = cost[cur], size, comp;
    checked[cur] = true;
    q.push(cur);
    while (!q.empty()) {
        cur = q.front();
        q.pop();
        size = adj[cur].size();
        for (int k = 0; k < size; k++) {
            comp = adj[cur][k];
            if (!checked[comp]) {
                checked[comp] = true;
                q.push(comp);
                mincost = min(mincost, cost[comp]);
            }
        }
    }
    costsum += mincost;
}

int main() {
    int n, m, k, fir, sec, i;
    cin >> n >> m >> k;
    initializer(n);

    for (i = 1; i <= n; i++)
        cin >> cost[i];
    while (m--) {
        cin >> fir >> sec;
        adj[fir].push_back(sec);
        adj[sec].push_back(fir);
    }

    for (i = 1; i <= n; i++)
        if (!checked[i]) bfs(i);
    if (k >= costsum) cout << costsum << '\n';
    else cout << "Oh no" << '\n';

    return 0;
}

AlgorithmalgorithmbaekjoonC++